package com.cat.chapter035;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;

/**
 * @author cat
 * @description https://leetcode.cn/problems/insert-delete-getrandom-o1-duplicates-allowed/
 * @create 2025/6/1 20:43
 * @since JDK17
 */
class RandomizedCollection {
    private static HashMap<Integer, HashSet<Integer>> map;
    private static ArrayList<Integer> list;
    public RandomizedCollection() {
        map = new HashMap<>();
        list = new ArrayList<>();
    }
    // 有 false, 无 true
    public boolean insert(int val) {
        HashSet<Integer> hashSet = map.get(val);
        boolean flag = hashSet == null;
        if (flag) { // 无
            hashSet = new HashSet<>();
            map.put(val, hashSet);
        }
        hashSet.add(list.size());   // 放入的下标
        list.add(val);
        return flag;
    }
    // 有true, 无false
    public boolean remove(int val) {
        HashSet<Integer> hashSet = map.get(val);
        if (hashSet == null) {  // 没有直接返回
            return false;
        }
        Integer valIndex = hashSet.iterator().next();   // 拿到val的任意一个下标
        Integer endVal = list.get(list.size() - 1); // 拿到最后一个数字
        HashSet<Integer> endValSet = map.get(endVal); // 最后一个值的哈希表
        if (endVal == val) {
            endValSet.remove(list.size() - 1);  // 将最后一个下标删除
        } else {    // 替换
            hashSet.remove(valIndex);
            endValSet.add(valIndex);
            endValSet.remove(list.size() - 1);
            list.set(valIndex, endVal);
        }
        list.remove(list.size() - 1);   // 删除最会一个
        if (hashSet.size() == 0) {  // 直接删
            map.remove(val);
        }
        return true;
    }

    public int getRandom() {
        return list.get(((int) (Math.random() * list.size())));
    }
}